package traverser;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * WikiTrie.java
 * Storage system for visited pages.  Also stores the previous search
 * term, or parent.  Should allow for sub O(log(n)) insertion and lookup.
 * 
 * Author: Dan Roberts
 * Last modified: 10/10/11
 */

public class WikiTrie {
	private final boolean DEBUG = false;
	
	int size = 0;
	
	TrieNode root = null;
	
	// How many entries in the trie?
	public int size() {
		return size;
	}
	
	// Add a word to the trie - max lg(n) time, average constant
	public void add(String word, String parent) {
		if (DEBUG) System.out.println("Adding " + word);
		if (root == null) {
			root = new TrieNode(word.charAt(0), null);
		}
		
		TrieNode iter = root;
		int i = 0;
		while (i < word.length()) {
			// We're on the correct path
			if (iter.value == word.charAt(i)) {
				if (DEBUG) System.out.print(word.charAt(i) + " ");
				i++;
				if (i < word.length()) {
					if (iter.center == null) {
						iter.center = new TrieNode(word.charAt(i), iter);
					}
					iter = iter.center;					
				}
				
			// The current path is less than the target, so veer right
			} else if (iter.value < word.charAt(i)) {
				if (DEBUG) System.out.print("right ");
				if (iter.right == null) {
					iter.right = new TrieNode(word.charAt(i), iter);
				}
				iter = iter.right;
				
			// The current path is more than the target, so veer left
			} else {
				if (DEBUG) System.out.print("left ");
				if (iter.left == null) {
					iter.left = new TrieNode(word.charAt(i), iter);
				}
				iter = iter.left;
			}
		}
		if (DEBUG) System.out.println();
		
		iter.isEndpoint = true;
		if (parent != null)
			iter.searchParent = lastNodeOf(parent);
		
		size++;
	}
	
	// Does the trie contain word?
	public boolean contains(String word) {
		return lastNodeOf(word) != null;
	}
	
	// Returns null if word is not in the trie
	private TrieNode lastNodeOf(String word) {
		if (DEBUG) System.out.println("Searching for " + word);
		TrieNode iter = root;
		int i = 0;
		while (i < word.length()) {
			if (iter == null) {
				// error, word is not in the trie.
				return null;
			}
			// correct path
			if (iter.value == word.charAt(i)) {
				if (DEBUG) System.out.print(iter.value + " ");
				i++;
				if (i < word.length()) 
					iter = iter.center;
				
			
			// less than the correct path (veer right)
			} else if (iter.value < word.charAt(i)) {
				if (DEBUG) System.out.print("right ");
				iter = iter.right;
				
			// more than the correct path (veer left)
			} else {
				if (DEBUG) System.out.print("left ");
				iter = iter.left;
			}
		}
		// Should now be at the bottom of the target.
		if (iter != null && iter.isEndpoint) {
			if (DEBUG) System.out.println("\nFound " + word);
			return iter;
		} else {
			if (DEBUG) System.out.println("\nCould not find " + word);
			return null;
		}
	}
	
	// What is the previous search tearm to word?
	public String parentOf (String word) {
		TrieNode lastNode = lastNodeOf(word);
		// Word is not in the trie
		if (lastNode == null) return null;
		
		// Word does not have a parent
		if (lastNode.searchParent == null) return null;
		
		return nodeToStr(lastNode.searchParent);
	}
	
	// Given a node, get the string that corresponds to it
	private String nodeToStr (TrieNode node) {
		if (node == null) {
			return null;
		}
		String word = "";
		word += node.value;
		while (node.trieParent != null) {
			if (node.trieParent.center == node) {
				word = node.trieParent.value + word;
			}
			node = node.trieParent;
		}
		return word;
	}
	
	// What search path was followed to get to word?
	public Stack<String> getSearchPath (String word) {
		Stack<String> path = new Stack<String>();
		while (word != null) {
			path.push(word);
			word = parentOf(word);
		}
		return path;
	}
	
	// Turn the contents of the trie into an arraylist
	// TODO: convert to using a queue	
	public ArrayList<String> inOrder () {
		ArrayList<String> list = new ArrayList<String>();
		inOrderVisit(root, list, "");
		return list;
	}
	
	// Visit the nodes in the trie, in order
	private void inOrderVisit (TrieNode iter, ArrayList<String> list, String word) {
		if (DEBUG) System.out.println(iter.value);
		if (iter.left != null) {
			if (DEBUG) System.out.println("left");
			inOrderVisit(iter.left, list, word);
		}
		if (iter.isEndpoint) {
			//if (DEBUG) System.out.println(word+iter.value);
			list.add(word + iter.value);
		}
		if (iter.center != null) {
			if (DEBUG) System.out.println("center");
			inOrderVisit(iter.center, list, word+iter.value);
			if (DEBUG) System.out.println("up");
		}
		
		if (iter.right != null)	{
			if (DEBUG) System.out.println("right");
			inOrderVisit(iter.right, list, word);
		}
		//if (DEBUG) System.out.println("After: " + word);
	}
	
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String a = "puppy";
		String [] b = {"cat", "dog", "foo", "bar", "moo"};
		String [] c = {"green", "orange", "blue", "pink", "red"};
		String [] d = {"pizza", "ice cream", "corndog"};
		
		WikiTrie test = new WikiTrie();
		test.add(a, null);
		for (int i = 0; i < b.length; i++) {
			test.add(b[i], a);
		}
		
		for (int i = 0; i < c.length; i++) {
			test.add(c[i], b[i]);
		}
		
		for (int i = 0; i < d.length; i++) {
			test.add(d[i], c[3]);
		}
		
		System.out.println("Contents of trie");
		for (String str : test.inOrder()) {
			System.out.println(str);
		}
		System.out.println();
		
		System.out.println("Contains puppy: " + test.contains(a));
		System.out.println("Contains pizza: " + test.contains("pizza"));
		System.out.println("Contains pink: " + test.contains("pink"));
		System.out.println("Contains red: " + test.contains("red"));
		System.out.println("Contains orange: " + test.contains("orange"));
		System.out.println("Contains pizzaz: " + test.contains("pizzaz"));
		System.out.println("Contains asdjf: " + test.contains("asdjf"));
		System.out.println("Parentof pizza: " + test.parentOf("pizza"));
	}
	
	static class TrieNode {
		char value;
		boolean isEndpoint = false;
		TrieNode left = null;
		TrieNode right = null;
		TrieNode center = null;
		TrieNode searchParent = null;  // Previous search term; come up with a better name
		TrieNode trieParent = null;
		
		public TrieNode (char value, TrieNode trieParent) {
			this.value = value;
			this.trieParent = trieParent;
		}
	}


}
	